package fun.coding.baozi.practice;
import java.util.PriorityQueue;
import java.util.Arrays;
import java.util.Comparator;
/*
 * Given set of n points (Xi, Yi), write a function to find k nearest points from origin.
 */
public class NearestPoints {

	public static void main(String[] args) {
		Point[] points = 
			{ 
				new Point(0, 0),  // D^2 = 0
				new Point(1, 1),  // D^2 = 2 
				new Point(1, -1), // D^2 = 2
				new Point(2, 2),  // D^2 = 8
				new Point(3, 4),  // D^2 = 25
				new Point(2, -1)  // D^2 = 5
			};

		int k = 5;
		
		PriorityQueue<Point> pQueue = new PriorityQueue<Point>(k, new Comparator<Point>() {
			@Override
			public int compare(Point p1, Point p2) {
			//	System.out.println("Point p1 is " + p1.x + ", " + p1.y);
			//	System.out.println("Point p2 is " + p2.x + ", " + p2.y);
				int sq1 = p1.x * p1.x + p1.y * p1.y;
				int sq2 = p2.x * p2.x + p2.y * p2.y;
				if (sq1 < sq2) {
					return 1;
				} else if (sq1 == sq2) {
					return 0;
				} else {
					return -1;
				}
			}
		});
		
		System.out.println("The set of points are: " + toString(points));
		
		Point[] result = findNearestPoints(points, k, pQueue);
		System.out.println("The " + k + " nearest points from origin are: " + toString(result));	
	}
	
	public static String toString(Point[] points) { 
		String result = "[";
		for (int i = 0; i < points.length; i++) {
			result += "(" + points[i].x + ", " + points[i].y + ")";
			if (i != points.length - 1) {
				result += ", ";
			}
		}
		result += "]";
		return result;
	} 
	
	public static Point[] findNearestPoints(Point[] points, int k, PriorityQueue<Point> pq) {
		for (int i = 0; i < k; i++) {
			pq.add(points[i]);
		//	System.out.println(pq);
		//	Point[] each = pq.toArray(new Point[i + 1]);
		//	System.out.println("Current PQ is" + toString(each));
		}
		
		//Point[] firstK = pq.toArray(new Point[k]);
		//System.out.println("The first k elements" + toString(firstK));
		
		for (int m = k; m < points.length; m++) {
			Point temp = pq.peek();
			if ((points[m].x * points[m].x + points[m].y * points[m].y) < (temp.x * temp.x + temp.y * temp.y)) {
				pq.poll();
				pq.add(points[m]);
			}
		}	
		Point[] pqToArray = pq.toArray(new Point[k]); 
		return pqToArray;
	}

}
